package com.example.javabasic.mianshi;

import com.sun.org.apache.xalan.internal.xsltc.dom.MultiValuedNodeHeapIterator;
import sun.net.www.HeaderParser;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MergeSortedLists {
    static class ListNode {
        int val;
        ListNode next = null;
        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public String toString() {
            // TODO: 写代码实现链表的toString方法
            StringBuilder builder = new StringBuilder();
            ListNode node = next;
            while(node!=null){
                builder.append("val=").append(node.val);
                node = node.next;
            }
            return builder.toString();
        }
    }

    public static ListNode[] covert(int[][] input) {
        // TODO: 写代码实现二维数组到链表数组的转换
        ListNode[] list = new ListNode[input.length];
        for (int i = 0; i < input.length; i++) {
            ListNode other = new ListNode(input[i][0]);
            ListNode node = other;
            for (int i1 = 1; i1 < input[i].length; i1++) {
                ListNode listNode = new ListNode(input[i][i1]);
                node.next = listNode;
                node = node.next;
            }
            list[i] = other;
        }
        return list;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        // TODO: 给一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。
        ListNode res = new ListNode();
        ListNode node = res;
        Map<Integer, ListNode> map = new HashMap<>();
        int[] arr = new int[lists.length];
        for (int i = 0; i < lists.length; i++) {
            arr[i] = lists[i].val;
            map.put(i, lists[i]);
        }
        //当map 元素都被取完  则完成拼接
        while (map != null && map.size() > 0) {
            int index = 0;
            int min = arr[0];
            //取出最小值. 如果对应链表取完了  给其赋值-1
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] != -1 && arr[i] < min) {
                    min = arr[i];
                    index = i;
                }
            }
            //取出的下标放入新值, 如果链表为空, 那么从map中删除元素
            if (map.get(index) != null) {
                arr[index] = map.get(index).val;
                if(map.get(index).next!=null){
                    map.put(index,map.get(index).next);
                }else{
                    map.remove(index);
                    arr[index] = -1;
                }
            } else {
                map.remove(index);
                if (index != -1) {
                    arr[index] = -1;
                }
            }
            //当前数组最小值追加到链表
            if(min<0){
                break;
            }
            node.val = min;
            //最小值放入node
            node = node.next = new ListNode();
        }
        return res;
    }

    public static ListNode mergeKLists2(ListNode[] lists) {
        //记录头指针
        ListNode node = new ListNode();
        ListNode other = node;
        Map<Integer, ListNode> map = new HashMap<>();
        for (int i = 0; i < lists.length; i++) {
            map.put(i, lists[i]);
        }
        int index = 0;
        while(map.size()>0){
            Integer min = null;
            Set<Map.Entry<Integer, ListNode>> entries = map.entrySet();
            for (Map.Entry<Integer, ListNode> entry : entries) {
                if(min == null){
                    min = entry.getValue().val;
                }
                if(entry.getValue().val<min){
                    min = entry.getValue().val;
                    index = entry.getKey();
                }
            }
            if(min == null){
                break;
            }
            ListNode n = new ListNode(min);
            other.next = n;
            other = other.next;

            //获取下个节点
            if(map.get(index)==null){
                break;
            }
            ListNode next = map.get(index).next;
            if(next == null){
                //当下个节点为null  删除元素
                map.remove(index);
            }else{
                //不为null 则放入map中
                map.put(index,next);
            }

        }
        return node;

    }




    public static void main(String[] args) {
        int[][] input = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        ListNode[] ln = covert2(input);
        ListNode output = mergeKLists2(ln);
        System.out.println(output.toString());
    }


    public static ListNode[] covert2(int[][] input) {
        // TODO: 写代码实现二维数组到链表数组的转换
        ListNode[] list = new ListNode[input.length];
        for (int i = 0; i < input.length; i++) {
            ListNode other = new ListNode(input[i][0]);
            ListNode node = other;
            for (int i1 = 1; i1 < input[i].length; i1++) {
                ListNode listNode = new ListNode(input[i][i1]);
                node.next = listNode;
                node = node.next;
            }
            list[i] = other;
        }
        return list;
    }
}